'''
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例一：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例二：
输入：head = [1,2]
输出：[2,1]

示例三：
输入：head = []
输出：[]

提示：
链表中节点的数目范围是 [0, 5000]
 -5000 <= Node.val <= 5000


1: 迭代法：  通过维护三个指针（前驱 prev、当前 curr、后继 next_temp），从前往后遍历链表，逐个反转节点的指向。
2：递归法：  从链表的末尾开始，逐层反转节点的指向，将当前节点的 next 节点的 next 指向当前节点。  时间复杂度是O(n)（每个节点递归一次），空间复杂度是O(n)（递归栈的深度为链表长度）。
'''

# 定义链表节点类
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

#对一个单链表进行反转 采用递归的方法 参数 head 是待反转链表的头节点。
def reverseList(head):
    # 递归终止条件：当前节点为 None 或只有一个节点
    if not head or not head.next:
        return head
    # 递归反转后面的链表
    reversed_head = reverseList(head.next)
    # 将当前节点的下一个节点的 next 指向当前节点
    head.next.next = head
    # 当前节点的 next 指向 None（避免循环）
    head.next = None
    #无论递归多少层，reversed_head 始终指向反转后链表的头节点（原尾节点），所以 return reversed_head 的作用就是把这个节点返回给调用者。
    return reversed_head


def create_linked_list(values):
    dummy = ListNode(0)
    current = dummy
    for val in values:
        current.next = ListNode(val)
        current = current.next
    return dummy.next

def print_linked_list(head):
    values = []
    current = head
    while current:
        values.append(str(current.val))
        current = current.next
    return " -> ".join(values)

# 示例 1
head1 = create_linked_list([1, 2, 3, 4, 5])
reversed_head1 = reverseList(head1)
print(print_linked_list(reversed_head1))  # 输出: 5 -> 4 -> 3 -> 2 -> 1

# 示例 2
head2 = create_linked_list([1, 2])
reversed_head2 = reverseList(head2)
print(print_linked_list(reversed_head2))  # 输出: 2 -> 1

# 示例 3
head3 = create_linked_list([])
reversed_head3 = reverseList(head3)
print(print_linked_list(reversed_head3))  # 输出: